package sort;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zxl
 * @version 1.0
 * @date 2021/12/5 16:09
 * 希尔排序   将数组进行分列，然后按列进行排序，排序后变成新的数组，再次分列
 * 步长规则：（n/2的k次方：n长度 k步骤）假设数组长度为16，第一步：8+8，第二步：4+4+4+4，第三步：8个2，第四步：16个1
 * 由插入排序实现
 */
public class ShellSorting {
    static int[] a = new int[]{54, 3, 5, 2, 11, 56, 32, 43, 12, 25, 76, 90, 31, 67, 45, 76, 53, 87, 21};

    public static void main(String[] args) {
        List<Integer> stepList = getStepList();
        for (Integer integer : stepList) {
            sort(integer);
        }
        for (int i : a) {
            System.out.print(i + " ");
        }
    }

    /**
     * 算法
     *
     * @param step
     */
    private static void sort(Integer step) {
        // 分列  对第几列的数据进行排序
        for (int col = 0; col < step; col++) {
            // 插入排序  起始值为第二列的数（第一列的数默认以排好） 每次增加步长的倍数
            for (int begin = col + step; begin < a.length; begin += step) {
                int cur = begin;
                // 当后面的同列的数小于前面的，则交换
                while (cur > col && a[cur] < a[cur - step]) {
                    int temp = a[cur];
                    a[cur] = a[cur - step];
                    a[cur - step] = temp;
                    cur -= step;
                }
            }
        }
    }

    /**
     * 计算步长
     *
     * @return
     */
    private static List<Integer> getStepList() {
        List<Integer> stepList = new ArrayList<>();
        int len = a.length;
        while ((len = len / 2) > 0) {
            stepList.add(len);
        }
        return stepList;
    }
}
